package leetcode_top;

import org.junit.Test;

public class Ex371 {
    class Solution1 {
        public int getSum(int a, int b) {
            int flag = 0, ta, tb;
            StringBuilder sb = new StringBuilder();
            while (a != 0 || b != 0) {
                ta = a & 1;
                tb = b & 1;
                if (ta == 0 && tb == 0) {
                    if (flag == 1) {
                        sb.insert(0, 1);
                    } else {
                        sb.insert(0, 0);
                    }                     
                    flag = 0;
                } else if (ta == 1 && tb == 0 || ta == 0 && tb == 1) {
                    if (flag == 1) {
                        sb.insert(0, 0);
                        flag = 1;
                    } else {
                        sb.insert(0, 1);
                        flag = 0;
                    }
                } else {
                    if (flag == 1) {
                        sb.insert(0, 1);
                    } else {
                        sb.insert(0, 0);
                    }
                    flag = 1;
                }
                a >>>= 1;
                b >>>= 1;
            }
            return Integer.parseInt(sb.toString(), 2);
        }
    }

    class Solution {
        public int getSum(int a, int b) {
            //a记录a与b的异或，b记录a和b的进位
            //进位可以使用按位与表示，但是实际的进位还需要左移一位
            int tmp;
            while (b != 0) {
                tmp = a;
                a ^= b;
                b = (tmp & b) << 1;
            }
            return a;
        }
    }

    @Test
    public void test() {
        Solution s = new Solution();
        System.out.println(s.getSum(11, 24141));        
    }
}
